1. Field of the Invention
The present invention relates to a random-number generating circuit and more particularly a random-number generating circuit used in non-contact IC cards and reader/writers for the non-contact IC cards.
2. Description of the Related Art
Of recent years, there have been provided a number of thin non-contact IC cards that have intelligent functions, rewritable memory functions and others. Non-contact IC cards are characterized by the fact that they are able to transmit data to and from a reader/writer without being physically connected to it. Non-contact IC cards are used, for example, as prepaid cards, door keys, commutation tickets for trains and buses, tickets for ski lifts, and the like.
In order to prevent illegal retrieval or modification of data stored in a non-contact IC card, the non-contact IC card and a reader/writer of the IC card perform processing of certifying each other before transmitting data between them. The reader/writer performs the mutual authentication processing for the IC card that sends back a predetermined response signal corresponding to a polling signal that has been sent by the reader/writer. As a method of the mutual authentication processing, a method of using cryptographic keys are known.
Mutual authentication processing using cryptography between a non-contact IC card and a reader/writer is described in the following. First, the reader/writer transmits a random number a generated therein to the non-contact IC card. The non-contact IC card converts the received random number a into a random number A, using its own cryptographic key, and sends the random number A back to the reader/writer. Using a cryptographic key shared with particular non-contact IC cards, the reader/writer processes the generated random number a to obtain a random number Axe2x80x2 and compares the obtained random number Axe2x80x2 with the returned random number A. If the random numbers A and Axe2x80x2 coincide, the reader/writer certifies that the non-contact IC card is valid.
Next, the non-contact IC card transmits the random number b generated therein to the reader/writer. In this case, the reader/writer converts the received random number b to a random number B, using its own cryptographic key, and sends the random number B back to the non-contact IC card. Using a cryptographic key shared with particular reader/writers, the non-contact IC card processes the generated random number b to obtain a random number Bxe2x80x2 and compares the obtained random number Bxe2x80x2 with the returned random number B. If the random numbers B and Bxe2x80x2 coincide, the reader/writer certifies that the reader/writer is valid.
A random-number generating circuit is built into the non-contact IC card and the reader/writer.
FIG. 10 is a circuit diagram of a random-number generating circuit 500 used in prior art. The random-number generating circuit 500 is a so-called 48-bit M-sequence random-number generating circuit. It comprises a 1-bit shift register 501, a 2-bit shift register 504, a 25-bit shift register 505, and a 20-bit shift register 506 that are cascaded (in tandem) together, and adders 507, 508, and 509 that constitute an addition circuit that inputs the sum of the outputs of the shift registers to the input terminal of the 20-bit shift register 506, which is on the first level.
The 1-bit shift register 501 comprises a flip-flop 502 and a transfer gate 503 that operate in synchronization with a clock signal CLK that is output from a clock circuit 510. When address 02E2H is selected by a CPU, which is not illustrated, and an address-signal line is switched from LOW to HIGH, the 1-bit shift register 501 outputs the output of the flip-flop 502 as random-number data D10.
The circuits of the 2-bit shift register 504, 25 bit shift register 505, and 20-bit shift register 506 are composed by connecting, in serial, a number of circuits that are the same as the 1-bit shift register 501, with the number being the number of shifts in each shift register. The 2-bit shift register 504 outputs random-number data D11, D12, when address 15F2H is selected. The 25-bit shift register 505 outputs random-number data D13-D17, D18-D115, D20-D27, and D28-D211, when addresses 15F2H, 15F3H, 15F4H, and 15F5H are selected. The 20-bit shift register 506 outputs random-number data D212-D215, D30-D37, and D38-D315, when addresses 15F5H, 15F6H, and 15F7H are selected.
Random numbers generated by the random-number generating circuit 500 described above have a generation pattern that is repeated with a predetermined period. Therefore, communication data transmitted between the reader/writer and the non-contact IC card can be tapped, and the generation pattern of random numbers can be identified. If the generation pattern of random numbers is identified, then even if the cryptographic key and the contents of the cryptographic processing are unknown, non-contact IC cards can be forged by using a table that associates the random number a with the random number A. Similarly, the reader writer can be forged by using a table that associates the random number b with the random number B.
In order to effectively prevent the forgery of the non-contact IC card and the reader/writer through the tapping of the communication data, there is required a random-number generating circuit such that the generation pattern can not be deciphered even if the communication data is tapped. However, if the random-number generating circuit is made complicated, then illegal decipherment of the generation pattern can be effectively prevented, but the circuit size becomes large. Particularly, the size of the built-in random-number generating circuit in non-contact IC cards is preferred to be smaller.
Further, the communication processing for a non-contact IC card is required to be completed during the time when the non-contact IC card is within the area where communication with the reader/writer is possible. Therefore, communication processing including the mutual authentication processing for a non-contact IC card is required to be processed faster than for an IC card that is used by inserting to a slot.
Also, in the case of non-contact IC cards, a plurality of non-contact IC cards may simultaneously exist within an area where communication with the reader/writer is possible. In this case, before communication processing including the mutual authentication processing, each non-contact IC card is required to perform some processing for avoiding its response signal crashing against the response signal issued from other non-contact IC cards. For example, each non-contact IC card outputs its response signal to the polling signal from the reader writer, with timing based on a random number that is generated within the non-contact IC card. To improve the speed of communication between the non-contact IC card and the reader/writer, a random-number generating circuit that operates at great speed is required.
The objects of the present invention are to contribute to miniaturization of the apparatus with a built-in random-number generating circuit with a simple configuration and to provide a random-number generating circuit that generates random-number data that has no regular pattern and is hard to predict, a non-contact IC card having the random-number generating circuit built therein, and a reader/writer for non-contact IC cards having the random-number generating circuit built therein.
The random-number generating circuit in a first embodiment in accordance with the present invention comprises a plurality of shift registers synchronized with a clock and cascaded together, a circuit that obtains the sum of the outputs of more than one of the shift registers and inputs the obtained sum to the input terminal of the shift register on the first stage, and a clock generating circuit that inputs a clock signal to each of the shift registers. The random-number generating circuit outputs, as random-number data, bit data output from the shift registers. One or more of the shift registers have external signal input means and a plurality of adders each that adds bit data input through the external signal input means to one or more bits of the bit data stored within. The bit data obtained by the adders are output as the random-number data.
The random-number generating circuit of this configuration generates random-number data, using the bit data flowing through external-signal lines, so that random-number data that has no regular pattern and is hard to predict can be generated.
In the random-number generating circuit in another embodiment in accordance with the present invention, the above clock generating circuit comprises a CLK circuit that generates a clock signal of a predetermined frequency and a PLL circuit that receives the clock signal generated by the CLK circuit as a reference-frequency signal. The output of the PLL circuit is input to each of the shift registers. The random-number generating circuit uses for a clock generating circuit the PLL circuit that outputs a clock signal of a frequency determined by the supplied source voltage until the frequency converges to the reference frequency. As a result, in an IC card having a built-in random-number generating circuit of the above second configuration, the value of the random-number data output immediately after the power is turned on can be varied by the dispersion of the constituent parts and the like.
In either the random-number generating circuit of the above first configuration or of the second configuration, a flip-flop that is a part of the above shift registers and operates in synchronization with a clock preferably has a first component that outputs HIGH as data output when the power is turned on and a second component that has the same drive and outputs LOW as data output when the power is turned on. The output terminals of both the first and second components are preferably connected to wire or transistors of the same writing capacity. In this way, the probability that the output data is HIGH (and the probability that the output data is LOW) when the power is turned on can be made 50%. By this means, an initial value output from each register becomes uniform when the power is turned on, so that the prediction of the random-number data becomes more difficult.
Further, a reset circuit is preferably additionally installed in the random-number generating circuit, and a logic circuit is preferably installed in the clock signal generating circuit. The reset circuit outputs a reset signal to each shift register, depending on the input of a reset-request signal. The logic circuit stops the output of the clock signal to each shift register, depending on a clock-stop signal and outputs the clock signal to each shift register, depending on a clock-operation signal. In this case, the clock signal can be stopped and activated depending on necessity. By this means, reading of a random number with predetermined timing becomes possible. Also, the bit data that is stored in each shift register can be reset.
The present invention also provides a non-contact IC card having one of the random-number generating circuits of the above configurations built within. This non-contact IC card has a control means that performs processing of communicating with a reader/writer, using the random-number data output from the random-number generating circuit. Predetermined signal lines that are used by the control means are connected to the above external-signal input terminals. Having one of the above random-number generating circuits built therein, the non-contact IC card can swiftly obtain random-number data that has no regular pattern and is hard to predict, so that high-speed communication processing with a corresponding reader/writer can be performed.
The present invention also provides a reader/writer used with above non-contact IC cards. The reader/writer has a control means that performs communication processing with a corresponding non-contact IC card by using random number output from the built-in random-number generating circuit. Predetermined signal lines used by the control means are connected to the external-signal input terminals. The reader/writer can swiftly obtain random-number data that has no regular pattern and is hard to predict, so that high-speed communication processing with a corresponding non-contact IC card can be performed.
Further, the present invention includes a method of testing an apparatus that has the above random-number generating circuit having the above reset circuit and the above clock generating circuit with the above logic circuit and that has a control means that performs predetermined processing by using random-number data output from the built-in random-number generating circuit and uses predetermined signal lines connected to the external-signal input terminals.
This testing method outputs a clock-stop signal into the logic circuit in the clock generating circuit, outputs a reset-request signal to the reset circuit, outputs a clock-operation signal into the logic circuit of the clock generating circuit, and performs test processing of the above apparatus, outputs a clock-stop signal into the logic circuit of the clock generating circuit, immediately after the completion of the test processing, reads random-number data output from an output means, and detects abnormalities in the system by comparing the read random-number data with reference data.
According to this testing method, the above random-number generating circuit is used as a testing circuit, so that a dedicated testing circuit is unnecessary, and miniaturization of the apparatus can be realized.